package likouJava;

//public class 排序链表 {
//    public ListNode sortList(ListNode head) {
//        if(head == null || head.next == null)return head;
//
//        //使用快慢指针将链表划分为两部分
//        ListNode fast = head, slow = head, pre = null;
//
//        while (fast != null && fast.next != null){
//            pre = slow;
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//        //断开链表
//        pre.next = null;
//
//        ListNode l1 = sortList(head);
//        ListNode l2 = sortList(slow);
//
//        //合并两个有序列表
//
//        return mergeTwoList(l1, l2);
//        }
//
//    private ListNode mergeTwoList(ListNode list1, ListNode list2) {
//        if (list1 == null && list2 ==null){
//            return null;
//        } else if (list1 == null) {
//            return list2;
//        } else if (list2 == null) {
//            return list1;
//        }
//        ListNode dummy = new ListNode(-1);
//        ListNode current = dummy;
//
//        while (list1 != null && list2 != null){
//            if (list1.val <= list2.val){
//                current.next = list1;
//                list1 = list1.next;
//            }else {
//                current.next = list2;
//                list2 = list2.next;
//            }
//            current =current.next;
//        }
//        if (list1 != null){
//            current.next = list1;
//        }else {
//            current.next = list2;
//        }
//        return dummy.next;
//    }
//}


public class 排序链表 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        //使用快慢指针将链表划分为两部分
        ListNode fast = head, slow = head, pre = null;

        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //断开链表
        pre.next = null;

        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        //合并两个有序列表

        return mergeTwoList(l1, l2);
    }

    private ListNode mergeTwoList(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        } else if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }

        if (list1.val <= list2.val) {
            list1.next = mergeTwoList(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoList(list1, list2.next);
            return list2;
        }
    }

}


